package airthmetic.exercise.arr;

import java.util.HashSet;

public class _26_删除有序数组中的重复项 {
    // 缓存思想 时间复杂度O(n) 空间复杂度O(n)
    public static int removeDuplicates(int[] nums) {
        int p = 0;
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                continue;
            } else {
                nums[p++] = nums[i];
                set.add(nums[i]);
            }
        }
        return p;
    }

    // 双指针思想 时间复杂度O(n) 空间复杂度O(1)
    public static int removeDuplicates2(int[] nums) {
        int p = 0;
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                nums[p++] = nums[i];
                max = nums[i];
                continue;
            }
            if (i > 0 && max == nums[i]) {
                continue;
            } else {
                nums[p++] = nums[i];
                max = nums[i];
            }
        }
        return p;
    }

    // 双指针思想 优化判断条件提前拿出来 时间复杂度O(n) 空间复杂度O(1)
    public static int removeDuplicates3(int[] nums) {
        if (nums == null){
            return 0;
        }
        if (nums.length == 1){
            return 1;
        }
        int p = 1;
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (max == nums[i]) {
                continue;
            } else {
                nums[p++] = nums[i];
                max = nums[i];
            }
        }
        return p;
    }


    public static int removeDuplicates4(int[] nums) {
        String a = "ads";
        char[] chars = a.toCharArray();
        if(nums == null){
            return 0;
        }
        if(nums.length == 1){
            return 1;
        }
        int j = 1;
        int max = nums[0];
        for(int i =1; i<nums.length; i++){
            int temp = nums[i];
            if(temp > max){
                max = temp;
                nums[j++] = nums[i];
            }
        }

        return j;
    }



    public static void main(String[] args) {
        int[] nums = new int[]{0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        System.out.println(removeDuplicates4(nums));
        for (int num : nums) {
            System.out.println(num);
        }
    }
}
